| 翻訳と辞書 |
| induced subgraph isomorphism problem ： ウィキペディア英語版 |
induced subgraph isomorphism problem
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.
==Problem statement==
Formally, the problem takes as input two graphs ''G''1=(''V''1, ''E''1) and ''G''2=(''V''2, ''E''2), where the number of vertices in ''V''1 can be assumed to be less than or equal to the number of vertices in ''V''2. ''G''1 is isomorphic to an induced subgraph of ''G''2 if there is an injective function ''f'' which maps the vertices of ''G''1 to vertices of ''G''2 such that for all pairs of vertices ''x'', ''y'' in ''V''1, edge (''x'', ''y'') is in ''E''1 if and only if the edge (''f''(''x''), ''f''(''y'')) is in ''E''2. The answer to the decision problem is yes if this function ''f'' exists, and no otherwise.
This is different from the subgraph isomorphism problem in that the absence of an edge in ''G''1 implies that the corresponding edge in ''G''2 must also be absent. In subgraph isomorphism, these "extra" edges in ''G''2 may be present.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「induced subgraph isomorphism problem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|